The present invention relates to a method and apparatus for implementing electronic cash through utilization of a telecommunication system.
An electronic funds transfer employing a telecommunication system is now coming into common use. In general, a certificate which is convertible into money at a financial institution (hereinafter referred to simply as a bank), such as a draft or check, has a symbolic function of its own (which guarantees its holder to the rights stated thereon). When handled in the telecommunication system, the certificate is digitized data, which can easily be copied and converted into money many times. This problem is encountered as well in the implementation of electronic cash such as a prepaid card, because the prepaid card can also be copied for illicit use to convert into money or purchase articles again and again.
As a solution to this problem, there has been proposed a scheme which employs a card having a computation facility and checks its double usage by suitably adapting data exchange between a card reader and the card during cashing procedure (Chaum, Fiat and Naor, "Untraceable Electronic Cash", Proc. of CRYPTO, '88, for example).
The above-mentioned Chaum, et al. scheme may be briefly summarized in the following outline. Incidentally, user's identification information (such as his account number, etc.) will hereinafter be represented by ID.
A description will be given first of the procedure for a user to have a bank issue electronic cash of a certain face value.
Step 1: The user creates k random numbers a.sub.i (where i=1, . . . , k) and uses a public one-way function g to obtain x.sub.i and y.sub.i from the following equations: EQU x.sub.i =g(a.sub.i) EQU y.sub.i =g(a.sub.i .sym.ID)
where i=1, . . . , k.
In the above, .sym. represents an Exclusive OR logic operation.
Step 2: The user computes, by the following equation, the product B.sub.i of a valve f(x.sub.i, y.sub.i) computed using a public one-way function f and the e-th power of a random number r.sub.i, and then presents the value B.sub.i to the bank. EQU B.sub.i =r.sub.1.sup.e .times.f(x.sub.i, y.sub.i) mod n,
where i=1, . . . , k
The calculation of B.sub.i is preprocessing for obtaining a signature of the bank to f(x.sub.i, y.sub.i) without allowing the bank to know its contents, and will hereinafter be called blind signature preprocessing. Here, a mod b generally represents the remainder of the division of an integer a by an integer b.
Step 3: The bank makes the user open his ID and k/2 random numbers a.sub.i and r.sub.i to confirm that the user has correctly executed Steps 1 and 2. The following description will be given on the assumption that the random numbers a.sub.i and r.sub.i are not opened for those i=1, . . . , k/2.
Step 4: The bank obtains the product of unopened k/2 values B.sub.i and raises it to the d-th power to compute a signature D as indicated by the following equation. At the same time, the bank withdraws the corresponding amount of money from the user's account. ##EQU1##
Step 5: The user computes, by the following equation, electronic cash C with the influence of the random number r.sub.i removed from the signature D. ##EQU2## At this time, the following equation holds: ##EQU3## The electronic cash obtained by this processing is equivalent to the value f(x.sub.i, y.sub.i) directly applied with the signature of the bank. Here, e, d and n are created by the band and satisfy the following equations.
n=P.times.Q PA1 l=LCM{P-1), (Q-1)}, and PA1 e.times.d=1 (mod l) PA1 e.sub.A .times.d.sub.A .tbd.1 (mod l), PA1 l=LCM{(P-1), (Q-1)}, and PA1 n=P.times.Q,
where P and Q are prime numbers and LCM{a, b} generally represents the least common multiple of a and b. The bank publishes the information e corresponding to the face value of the electronic cash C and the key n and keeps the key d strictly confidential.
The procedure for the user to pay with the electronic cash C at a shop is as follows:
Step 6: The user presents the electronic cash C to the shop.
Step 7: The shop creates and transmits a random bit string E.sub.1, . . . , k.sub.k/2 to the user.
Step 8: For an unopened item i in 1.ltoreq.i.ltoreq.k/2, the user presents, to the shop, a.sub.i and y.sub.i when E.sub.i =1, and x.sub.i and (a.sub.i .sym.ID) when E.sub.i =0.
Step 9: The shop checks the validity of the electronic cash C by the following equation, using the user's response and the public information e and n. ##EQU4##
The method of settlement between the shop and the bank is as follows:
Step 10: The shop later presents the electronic cash C, the bit string E.sub.1, . . . , E.sub.k/2 and the user's response (a.sub.i and y.sub.i, or x.sub.i and (a.sub.i .sym.ID)) and receives payment of the amount of money concerned.
Step 11: The bank stores the electronic cash C, the bit string E.sub.1, . . . , E.sub.k/2 and a.sub.i (when E.sub.i =1), or (a.sub.i .sym.ID) (when E.sub.i =0).
The scheme described above has its features in that it maintains user privacy and permits checking double usage of the electronic cash.
Now, a description will be given first of the security for user privacy. Since the information B is obtained by randomizing the value f(x.sub.i, y.sub.i) with random numbers, the bank and a third party cannot assume the value f(x.sub.i, y.sub.i) from the information B. Further, even if the bank and the shop should conspire, they could not associate the electronic cash C with the signature D. In other words, it is impossible to know who issued the electronic cash C. Thus, the method proposed by Chaum, et al. does not allow the originator (i.e. the user) to be traced back, and hence ensures the privacy of the user, such as his propensity to consume. The signature scheme used here will hereinafter be referred to as the "blind signature" scheme.
As the blind signature scheme, for instance, Chaum proposes in U.S. Pat. No. 4,759,063 the following blind signature scheme utilizing the RSA encryption scheme.
A user randomizes a message M with a one-way function Fe.sub.A expressed by the following equation (1) using a random number r: EQU W=Fe.sub.A (M)=r.sup.e.sbsp.A .times.M mod n (1)
and sends the resulting randomized message W to a bank. This processing by the one-way function Fe.sub.A is the blind signature preprocessing.
The bank signs the randomized message W with a signature function De.sub.A expressed by the following equation (2) to obtain a signed randomized message .OMEGA., which is sent to the user. EQU .OMEGA.=De.sub.A (W)=W.sup.d.sbsp.A mod n (2)
The user processes the signed randomized message .OMEGA. with a blind signature postprocessing function He.sub.A expressed by the following equation (3): EQU He.sub.A (.OMEGA.)=.OMEGA./r mod n (3)
In the above, e.sub.A, d.sub.A and n in Eqs. (1), (2) and (3) are to satisfy the following conditions:
where P and Q are prime numbers, LCM{a, b} is the least common multiple of a and b, d.sub.A is a secret key, and e.sub.A and n are public keys.
Eq. (3) can be modified as follows: EQU He.sub.A (.OMEGA.)=He.sub.A {De.sub.A (Fe.sub.A (M))}.tbd.(r.sup.e.sbsp.A .times.M).sup.d.sbsp.A /r.tbd.r.sup.e.sbsp.A.sup..times.d.sbsp.A .times.M.sup.d.sbsp.A /r.tbd.M.sup.d.sbsp.A (mod n) (4)
The right side of Eq. (4) is evidently the replacement of W in Eq. (2) with M. Accordingly, the following equation holds: EQU He.sub.A (.OMEGA.)=De.sub.A (M) (5)
These equations (1), (2) and (3) are representative of the blind signature procedure, and Eq. (4) proves that the blind signature is possible. That is to say, the influence of the random number r can be removed from the signed randomized message .OMEGA. by processing it with the blind signature postprocessing function He.sub.A. Hence, it is possible to obtain the same signed message De.sub.A (M) as the message M directly signed by the bank using the signature function De.sub.A.
Next, a description will be given of the detection of double usage of the electronic cash C. The bank compares the electronic cash C sent from the shop with all electronic cash already stored in a memory to check whether the same electronic cash C has been used twice. Suppose that the user has invalidly used the electronic cash twice. Then, since a.sub.i for E.sub.i =1 or (a.sub.i .sym.ID) for E.sub.i =0 has been stored in the memory of the bank corresponding to the first electronic cash C, the identification information ID can be obtained by computing a.sub.i .sym. (a.sub.i .sym.ID) if E.sub.i for the first use of the electronic cash C and E.sub.i for the second use differ. Since the bank makes an inquiry of k/2 bits, the probability of coincidence through all bits (i=1 to k/2) between the two E.sub.i 's, that is, the possibility that the user's ID cannot be computed from the electronic cash C used twice invalidly, is 2.sup.-k/2.
In addition to the requirement for the one-way property of the functions f and g, the above-described Chaum, et al. scheme requires the collision-free property of two arguments, that is, difficulty in finding (x, y) and (x', y') which satisfy Z=f(x, y)=f(x', y') for securing safety against double usage of electronic cash. However, no method has been proposed so far which constructs the one-way functions which satisfy the collision-free property of the two arguments.